package com.itzmn.newcode.offer1;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/20 15:41
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 二叉搜索树的后序遍历序列
 *
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 *
 * 思路：3，6,5,12,15,10  后序遍历
 *
 *  最后一个是根，每一个节点都是一个二叉搜索树。
 *
 */
public class _23_PostOrderTraversalSequenceOfBinarySearchTree extends Tree{

    public static void main(String[] args) {

        new _23_PostOrderTraversalSequenceOfBinarySearchTree().test();
    }

    private void test() {
        TreeNode binarySearchTree = createBinarySearchTree(new int[]{5, 6, 2, 7, 3, 9});
        InOrderTraversal(binarySearchTree);
        System.out.println();
        PostOrderTraversal(binarySearchTree);

        VerifySquenceOfBST(new int[]{2,3,5,6,7,9});
    }

    public boolean VerifySquenceOfBST(int [] sequence) {

        int length = sequence.length;
        if (length == 0){
            return false;
        }

        boolean check = check(sequence, 0, length - 1);

        return check;
    }
    private boolean check(int[] sequence,int start,int end){
        if (start>=end){
            return true;
        }
        int rootVal = sequence[end];
        int index = start;
        // 得到根的左子树的节点
        for (int i=start;i<end;i++){
            if (sequence[i] >= rootVal){
                break;
            }
            index++;
        }
        //剩下的都要大于等于根，都是右子树节点
        for (int i=index;i<end;i++){
            if (sequence[i]<rootVal){
                return false;
            }
        }

        return check(sequence,start,index-1) && check(sequence,index,end-1);
    }

}
